package com.mlh.dp.背包问题.完全背包;

import java.util.Arrays;

/**
 * @author 缪林辉
 * @date 2024/4/20 11:05
 * @DESCRIPTION
 */
// 给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。
// 请你从 nums 中找出并返回总和为 target 的元素组合的个数。
// 题目数据保证答案符合 32 位整数范围。
// 输入：nums = [1,2,3], target = 4
// 输出：7
// 解释：
// 所有可能的组合为：
// (1, 1, 1, 1)
// (1, 1, 2)
// (1, 2, 1)
// (1, 3)
// (2, 1, 1)
// (2, 2)
// (3, 1)
// 请注意，顺序不同的序列被视作不同的组合。
public class 组合总和4 {
    //方法一写错了，第一层循环写的是背包物品，这样是集合，而不是组合了
    public static int method1(int[] nums, int target) {
        int[] dp = new int[target + 1];//不同目标整数的组合数
        dp[0]=1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = nums[i]; j <=target ; j++) {
                dp[j]=dp[j]+dp[j-nums[i]];
            }
        }
        return dp[target];
    }
    //因此第一层循环要写容量，这样才是组合数
    public static int method2(int[] nums, int target) {
        int[] dp = new int[target + 1];//不同目标整数的组合数
        dp[0]=1;//初始化  不需求实际意义，要带入到递推公式的本身来推导
        for (int i = 1; i <=target; i++) {//背包容量
            for (int j = 0; j <nums.length ; j++) {//物品种类
                if(i>=nums[j]){//容量大于该物品的体积才能装得下该物品
                    dp[i]=dp[i]+dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }

    //因为纯完全背包求得装满背包的最大价值是多少，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！所以两种遍历顺序都可以满足要求
    //而这种凑成总和的组合数 或者 凑成总和的排列数 就需要关注遍历顺序了
    //完全背包的循环顺序的背后含义：
    //如果求组合数就是外层for循环遍历物品，内层for遍历背包。
    // 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
    public static int practice(int[] nums, int target) {
        int[]dp=new int[target+1];
        dp[0]=1;
        for (int i = 1; i <=target; i++) {
            for (int j = 0; j <nums.length; j++) {
                if(i>=nums[j]){
                    dp[i]+=dp[i-nums[j]];
                }
            }
        }
        return dp[target];
    }
}
